package com.lucien.Sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 基数排序是使用空间换时间的经典算法
 *
 */
public class RadixSort {
    public static void main(String[] args) {
        int [] arr = {53,3,542,748,14,214};
//        radixSortTest(arr);
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
//            testTime();
    }

    //基数排序
    public static void radixSortTest(int [] arr){
        /** 定义一个二维数组，表示10个桶，每个桶就是一个一维数组
            二维数组包含10个一维数组，为了防止放数据的时候，数据溢出
            每一个一维数组的大小定义为arr.length
         */
        int [][] bucket = new int [10][arr.length];
        //定义一个一维数组，用来记录实际存放了多少个数据
        int [] bucketCount = new int [10];

        //第一轮(针对每个元素的个位进行排序处理)
        for (int j = 0;j<arr.length;j++){
            int bitElement = arr[j] % 10;
            bucket[bitElement][bucketCount[bitElement]] = arr[j];
            bucketCount[bitElement]++;
        }
        //按照这个桶的顺序(一维数组的数据依次取出数据，放回到原来数组)
        int index = 0;
        //遍历每一个桶，并将有数据的桶中的元素，放回到原来的数组中
        for (int k = 0;k<bucketCount.length;k++){
            //如果桶中有数据才放入原数组
            if (bucketCount[k] != 0 ){
                //循环该桶即第k个桶(即第k个一维数组)
                for (int l = 0;l<bucketCount[k];l++){
                    //取出元素放到arr中
                    arr[index]=bucket[k][l];
                    index++;
                }
            }
            //第一轮处理后，需要将每个bucketCount[k]置为0
            bucketCount[k] = 0;
        }
        System.out.println("第一轮处理后的arr："+Arrays.toString(arr));

//=================================================

        //第二轮(针对每个元素的个位进行排序处理)
        for (int j = 0;j<arr.length;j++){
            int bitElement = arr[j] /10 % 10;
            bucket[bitElement][bucketCount[bitElement]] = arr[j];
            bucketCount[bitElement]++;
        }
        //按照这个桶的顺序(一维数组的数据依次取出数据，放回到原来数组)
        index = 0;
        //遍历每一个桶，并将有数据的桶中的元素，放回到原来的数组中
        for (int k = 0;k<bucketCount.length;k++){
            //如果桶中有数据才放入原数组
            if (bucketCount[k] != 0 ){
                //循环该桶即第k个桶(即第k个一维数组)
                for (int l = 0;l<bucketCount[k];l++){
                    //取出元素放到arr中
                    arr[index]=bucket[k][l];
                    index++;
                }
            }
            //第一轮处理后，需要将每个bucketCount[k]置为0
            bucketCount[k] = 0;
        }
        System.out.println("第二轮处理后的arr："+Arrays.toString(arr));

//================================================

        //第三轮(针对每个元素的个位进行排序处理)
        for (int j = 0;j<arr.length;j++){
            int bitElement = arr[j] /100 % 10;
            bucket[bitElement][bucketCount[bitElement]] = arr[j];
            bucketCount[bitElement]++;
        }
        //按照这个桶的顺序(一维数组的数据依次取出数据，放回到原来数组)
        index = 0;
        //遍历每一个桶，并将有数据的桶中的元素，放回到原来的数组中
        for (int k = 0;k<bucketCount.length;k++){
            //如果桶中有数据才放入原数组
            if (bucketCount[k] != 0 ){
                //循环该桶即第k个桶(即第k个一维数组)
                for (int l = 0;l<bucketCount[k];l++){
                    //取出元素放到arr中
                    arr[index]=bucket[k][l];
                    index++;
                }
            }
            //第三轮处理后，需要将每个bucketCount[k]置为0
            bucketCount[k] = 0;
        }
        System.out.println("第三轮处理后的arr："+Arrays.toString(arr));

    }


    public static void radixSort(int [] arr){
        //得到最大的数的位数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i]>max){
                max = arr[i];
            }
        }
        //得到最大数的是几位数
        int maxLength = (max+"").length();
        int [][] bucket = new int [10][arr.length];
        int [] bucketCount = new int [10];
        for (int i = 0,n = 1; i < maxLength; i++,n *= 10) {
            for (int j = 0;j<arr.length;j++){
                int bucketElement = arr[j] / n % 10;
                bucket[bucketElement][bucketCount[bucketElement]] = arr[j];
                bucketCount[bucketElement]++;
            }
            int index = 0;
            for (int k =0;k<bucketCount.length;k++){
                if (bucketCount[k] != 0){
                    for (int l =0;l<bucketCount[k];l++){
                        arr[index]=bucket[k][l];
                        index++;
                    }
                }
                bucketCount[k] = 0;
            }
//            System.out.println("第"+i+"轮排序后arr："+Arrays.toString(arr));
        }
//        System.out.println("排序后arr："+Arrays.toString(arr));
    }

    //时间测试
    public static void testTime(){
        int [] arr = new int [8000000];
        int [] temp = new int[arr.length];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String str1 = simpleDateFormat.format(date1);
        System.out.println("排序前的时间是："+date1);

        radixSort(arr);

        Date date2 = new Date();
        String str2 = simpleDateFormat.format(date2);
        System.out.println("排序前的时间是："+date2);
    }
}
